// 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
// 要求时间复杂度为O(n)。

/**
 * @param {number[]} nums
 * @return {number}
 */

// nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
// dp = [-2, 1, -2, 4, 3, 5, 6, 1, 5]
// dp(n) =
//   dp[n] = nums[n] + max(dp[n - 1], 0)
var maxSubArray = function (nums) {
  if(nums.length == 0){
    return 0
  }
  var dp = [nums[0]]
  for (let i = 1; i < nums.length; i++) {
    dp.push(nums[i] + Math.max(dp[i-1],0))
  }
  return Math.max(...dp)
};
